package com.xj.algorithm.leetcode;

import java.util.Arrays;

/**
 * 数组拆分 I
 */
public class L561_配对数据的最小值的累加和最大 {

    /**
     * 给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从1 到 n 的 min(ai, bi) 总和最大。

     示例 1:

     输入: [1,4,3,2]

     输出: 4
     解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).
     提示:

     n 是正整数,范围在 [1, 10000].
     数组中的元素范围在 [-10000, 10000].
     */
    public static void main(String[] args) {
        int[] nums=new int[]{1,4,3,2};
        System.out.println(arrayPairSum(nums));
    }

    /**
     * 自己的解法：排序，小小组合，得到最小值的和的最大值
     *
     * 官方思路：a-b配对产生的总损失最小化，那么总金额现在将达到最大值。
     * 只有当为配对选择的数字比数组的其他元素更接近彼此时，才有可能将每个配对中的损失最小化。
     * @param nums
     * @return
     */
    public static int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int length=nums.length;
        int sum=0;
        for(int i=0;i<length;i=i+2){
            sum=sum+nums[i];
        }
        return sum;
    }

}
